#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;

int minPathSum(vector<vector<int>>& grid) 
{
  int m = grid.size();
  if(m<1)
    return 0;
  int n = grid[0].size();
  if(n<1)
    return 0;

  vector<vector<int>> ret;
  
  for(int i=0; i<m; ++i)
  {
    ret.push_back( vector<int> (n,0) );
    for(int j=0; j<n; ++j)
    {
      if(0==i && 0==j)
      {
        ret[0][0] = grid[0][0];
      }
      else if(0==i && j>0 )
      {
        ret[i][j] = ret[i][j-1] + grid[i][j];
      }
      else if( i>0 && 0==j) 
      {
        ret[i][j] = ret[i-1][j] + grid[i][j];
      }
      else if(i>0 && j>0)
      {
        int min = ret[i-1][j]<=ret[i][j-1] ? ret[i-1][j] : ret[i][j-1];
        ret[i][j] = min + grid[i][j];
      }
    }
  }
  
  return ret[m-1][n-1];

}



int main(int argc,char *argv[])
{

  vector<vector<int>> g;
  g.push_back( vector<int> {1,4,8,6,2,2,1,7} );
  g.push_back( vector<int> {4,7,3,1,4,5,5,1} );
  g.push_back( vector<int> {8,8,2,1,1,8,0,1} );
  g.push_back( vector<int> {8,9,2,9,8,0,8,9} );
  g.push_back( vector<int> {5,7,5,7,1,8,5,5} );
  g.push_back( vector<int> {7,0,9,4,5,6,5,6} );
  g.push_back( vector<int> {4,9,9,7,9,1,9,0} );






  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  //
  int ret  = minPathSum(g);

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;

  cout<<ret<<endl;



  return 0;
}
